% \section{Resultados}
% 
% O ambiente de testes do projeto tem a seguinte configuração:
% 
% \begin{table}[H]
% \begin{center}
% \caption{Ambiente de testes.}
% \label{tab:env}
% \begin{tabular}{|l|l|}
% \hline
% Computador & Asus Q550L. Intel Core i7-4500U. 8GB DDR3. \\ \hline
% OS / kernel & Ubuntu 13.10 x86\char`_64 / 3.11.0-15-generic \\ \hline
% Compilador & gcc 4.8.1 \\ \hline
% Relic & relic-0.3.5 \\ \hline
% GMP & 2:5.1.2+dfsg amd64. \emph{Multiprecision arithmetic library} \\
% \hline
% \end{tabular}
% \end{center}
% \end{table}
% 
% O uso da biblioteca GMP otimiza consideravelmente as funções da Relic.
% 
% A cada passo de implementação e otimização dos algoritmos, foi realizado testes
% para garantir a corretude dos componentes e uma coleta de dados consistente. O
% artefato de testes foi desenvolvido em um ambiente fornecido pela própria
% biblioteca Relic e verificava asssertivas sobre propriedades de anéis de
% polinômio.
% 
% Após a implementação otimizada do TFQS, chegou-se à comparação com o
% teste de Miller-Rabin, algoritmo padrão da Relic. Nesta análise, foram
% necessários alguns ajustes para igualar o \emph{setup} dos algoritmos.
% Inicialmente, as rodadas do teste de Miller-Rabin estavam configuradas para uma
% probabilidade de erro de $2^{-80}$, sendo necessário um ajuste no número de
% rodadas para se equiparar ao erro do TQFS, $2^{-100}$.
% 
% 
% \begin{figure}[H]
% \begin{center}
% 	\includegraphics[width=0.8\textwidth]{img/gen-fix2.eps}
% 	\caption{Gerador de primo com teste Rabin vs. TFQS.}
% 	\label{fig:gen-fix}
% \end{center}
% \end{figure}
% 
% Na comparação dos resultados obtidos (Figura~\ref{fig:gen-fix}), nota-se que o
% TFQS é mais veloz para teste de inteiros de até 256 \emph{bits}. Neste
% intervalo, obteve-se uma redução de cerca de 30\% no tempo de execução. A partir
% de 512 \emph{bits}, o Miller-Rabin passa a ser mais eficiente.
% 
% Em uma visão panorâmica, o TFQS pode ser delimitado pelo custo de
% uma exponenciação modular em anel de polinômio por rodada. De maneira
% semelhante, o teste de Miller-Rabin pode ser delimitado por uma exponenciação
% modular simples por rodada.






\section{Results}

The project testing environment has the following configuration:

\begin{table}[H]
\begin{center}
\caption{Tests Enviroment.}
\label{tab:env}
\begin{tabular}{|l|l|}
\hline
Computer & Asus Q550L. Intel Core i7-4500U. 8GB DDR3. \\ \hline
OS / kernel & Ubuntu 13.10 x86\char`_64 / 3.11.0-15-generic \\ \hline
Compiler & gcc 4.8.1 \\ \hline
Relic & relic-0.3.5 \\ \hline
GMP & 2:5.1.2+dfsg amd64. \emph{Multiple Precision arithmetic library} \\
\hline
\end{tabular}
\end{center}
\end{table}

The use of GMP library enhances considerably the Relic functions.

In each step of algorithms implementation and optimization, tests were carried
out to assure the correctness of components and a
consistent data collection. The test artifact was conducted in an
environment provided by the very Relic library and verifies polynomial rings
properties assertions. 

After the optimized implementation of SQFT, came to the comparison with 
Miller-Rabin test, Relic standard algorithm for primality test. In this
analysis, were required some adjustments to match both algorithms setup.
Initially, the rounds of the Miller-Rabin test were configured for an error 
probability of $2^{-80}$, so an adjustment in the number of 
rounds to equal SQFT error, $2^{-100}$, was necessary.

\begin{figure}[H]
\begin{center}
	\includegraphics[width=0.8\textwidth]{img/gen-fix2.eps}
	\caption{Prime Generation Miller-Rabin vs. TFQS.}
	\label{fig:gen-fix}
\end{center}
\end{figure}

Comparing the results obtained (Figure~\ref{fig:gen-fix}), we observe that the 
SQFT is faster for integers up to 256 bits. in this 
range, we obtained a runtime reduction average of 30\%.
From 512 bits on, the Miller-Rabin becomes more efficient. 

In an overview, the SQFT may be bounded by the cost of 
a modular exponentiation in polynomial ring per round. Similarly, the
Miller-Rabin test may be bounded by a simple modular exponentiation per round.

